package com.leetcode.根据算法进行分类.动态规划算法相关;

import java.util.HashSet;

/**
 * @author: ZhouBert
 * @date: 2021/2/19
 * @description: 467. 环绕字符串中唯一的子字符串
 * https://leetcode-cn.com/problems/unique-substrings-in-wraparound-string/
 */
public class B_467_环绕字符串中唯一的子字符串 {

	public static void main(String[] args) {
		B_467_环绕字符串中唯一的子字符串 action = new B_467_环绕字符串中唯一的子字符串();
		test1(action);
		test2(action);
	}

	public static void test1(B_467_环绕字符串中唯一的子字符串 action) {
		// 2
		String p = "cac";
		int res = action.findSubstringInWraproundStringByDP(p);
		System.out.println("res = " + res);
	}

	public static void test2(B_467_环绕字符串中唯一的子字符串 action) {
		// 3
		String p = "zab";
		int res = action.findSubstringInWraproundStringByDP(p);
		System.out.println("res = " + res);
	}


	/**
	 * 暴力解法：
	 * 将 p 所有子串求出，然后一个个去比较。这样是 O(n^2)(求出所有的子串是 O(n) 但是同时还需要比较)
	 * 通过观察，发现：当一个子串符合条件以后，其所有的部分字串都满足条件（可以直接算出而不用与 p 进行匹配）
	 * 当求出子串后，发现仍然存在相互中间部分重叠的情况：
	 * 此时我想到用前缀树，但是从前缀树求得所有子串的个数却不容易。
	 * 看来得用其他的办法了！
	 *
	 * @param p
	 * @return
	 */
	public int findSubstringInWraproundString(String p) {
		//保留子串（为了防止重复计算）
		HashSet<String> set = new HashSet<>();
		char[] chars = p.toCharArray();
		int len = chars.length;
		int begin = 0, end = 1;
		char lastC = chars[begin];
		while (end < len) {
			if (chars[end] == lastC + 1 || chars[end] == lastC - 25) {
				//此时符合

			} else {
				String str = new String(chars, begin, end - begin);
				if (!set.contains(str)) {
					set.add(str);
				}
				begin = end;

			}
			lastC = chars[end++];
		}
		String str = new String(chars, begin, end - begin);
		if (!set.contains(str)) {
			set.add(str);
		}

		//接下来就木有办法了！
		return 0;
	}


	/**
	 * 看了下题解以及相关说明，知晓了 动态方程：
	 * dp[i] 是以 26个字母中 i 处结尾的子串的个数。
	 * 这样能解决两个问题：
	 * 1.res = dp[i-> len]
	 * 2.重复子串的覆盖：eg. 当第二个 a 的个数 > 当第一个 a 的个数时，取最大值
	 * （如果 dp[i] 记录的是最大长度，也可以解决重复字串的问题！
	 * 因为规律是固定的，按照 abcde... 所以求出最大长度，也就相当于求出了
	 * 以字母结尾的子串个数。
	 * 正因为有这个规律，降低了题目的难度！
	 * 【这里有一条重要的经验：以 c 结尾的字串可以保证与 以 b 结尾的字串完全去重！】
	 * ）
	 *
	 * @param p
	 * @return
	 */
	public int findSubstringInWraproundStringByDP(String p) {
		if (p == null || p.length() == 0) {
			return 0;
		}
		// 通过 dpMaxLen 求出 以 字母结尾的最大个数
		// 用来表示：以 字母结尾的最大长度
		int[] dpMaxLen = new int[26];
		char[] chars = p.toCharArray();
		int len = chars.length;
		int begin = 0, end = 1;
		dpMaxLen[chars[begin] - 'a'] = 1;
		while (end < len) {
			int index = chars[end] - 'a';
			if (chars[end] == chars[end - 1] + 1 || chars[end] == chars[end - 1] - 25) {
				//如果具有连续性
				dpMaxLen[index] = Math.max(dpMaxLen[index], ++end - begin);
			} else {
				dpMaxLen[index] = Math.max(dpMaxLen[index], 1);
				begin = end;
				end++;
			}
		}
		int res = 0;
		for (int i = 0; i < 26; i++) {
			res += dpMaxLen[i];
		}
		return res;
	}

}
